package simple;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/9/13 17:27
 */
public class No303_区域和检索 {
    public static void main(String[] args) {
        int[] nums = new int[]{4, 1, 5, 3, 7, 2, 6, 1, 9};
        Solution303 solution303 = new Solution303(nums);
        int i = solution303.sumRange(0, 2);
        System.out.println();
    }
}

class Solution303 {
    //前缀和  O(n) + O(1)
    //树状数组: O(n) + O(logn)
    int[] sums;//前缀和数组
    public Solution303(int[] nums) {
        //开始
        sums = new int[nums.length + 1];//索引从1开始
        //遍历nums,填充sums
        for (int i = 0; i < nums.length; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
    }

    public int sumRange(int i, int j) {//索引从0开始
        // i=5,j=7   1-7   -    1-4
        //
        return sums[j + 1] - sums[i + 1 - 1];
    }
}





    ////中等理解,树状数组
    //int[] treeS;//树状数组
    //public Solution303(int[] nums) {
    //    //初始化
    //    treeS = new int[nums.length + 1];//索引从1开始
    //    int[] preSum = new int[nums.length + 1];
    //    for (int i = 1; i < treeS.length; i++) {
    //        //获取当前数
    //        int data = nums[i - 1];//nums索引从0开始
    //        preSum[i] = preSum[i - 1] + data;
    //        //初始化树状数组
    //        treeS[i] = preSum[i] - preSum[i - lowBit(i)];
    //    }
    //}
    //
    ////获取前缀和
    //public int getSum(int[] treeS, int index) {
    //    int sum = 0;
    //    while (index > 0) {
    //        sum += treeS[index];
    //        index -= lowBit(index);
    //    }
    //    return sum;
    //}
    //
    //public int sumRange(int i, int j) {//从0开始
    //    //从1开始   5-7    7  - 4
    //    int b = getSum(treeS, j + 1);
    //    int a = getSum(treeS, i + 1 - 1);
    //    return b - a;
    //}
    //
    //public int lowBit(int x) {
    //    return x & (-x);
    //}